import java.util.List;

public class MySingleList {

     static class ListNode {
         int val;//存储数据
         ListNode next;//存储下一个节点的地址
          ListNode(int val){
              this.val = val;
         }
     }
    // 1、无头单向非循环链表实现
      public ListNode head;
     public void createLink() {
         ListNode node1 = new ListNode(15);
         ListNode node2 = new ListNode(22);
         ListNode node3 = new ListNode(90);
         ListNode node4 = new ListNode(35);
         node1.next = node2;
         node2.next = node3;
         node3.next = node4;
         node4.next = null;
         head = node1;
     }
    public void display() {
        ListNode cur = head;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    public void display(ListNode newHead) {
        ListNode cur = newHead;
        while(cur != null) {
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
         ListNode cur = head;
         if (cur != null) {
             if (cur.val == key) {
                 return true;
             }
             cur = cur.next;
         }
         return false;
    }
        //头插法
        public void addFirst(int data){
            ListNode node = new ListNode(data);
            node.next = head;
            head = node;
        }
    //尾插法
       public void addLast(int data) {
          ListNode node = new ListNode(data);
          if (head == null) {
              head = node;
              return ;
          }
            ListNode tail = head;
            while (tail.next != null) {
                   tail = tail.next;
            }
            tail.next = node;

       }

    //得到单链表的长度
    public int size() {
         int count = 0;
         ListNode cur = head;
         while (cur != null) {
             count++;
             cur = cur.next;
         }
        return count;

    }
       //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
                checkIndex(index);
                if (index == 0) {
                    addFirst(data);
                    return ;
                }
                if (index == size()) {
                    addLast(data);
                    return ;
                }
                ListNode pre = findListSubone(index);
                ListNode node = new ListNode(data);
                node.next = pre.next;
                pre.next = node;
        }
        //找index下标上一个节点
        private ListNode findListSubone(int index) {
                ListNode cur = head;
                int count = 0;
                while (count != index-1) {
                    cur = cur.next;
                    count++;
                }
                return cur;
        }
         public void checkIndex(int index) throws ListIndexOutofException{
            if (index < 0|| index > size()) {
                throw new ListIndexOutofException("index位置不合法");
            }
         }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
         if (head == null) {
             return ;
         }
         if (head.val == key) {
             head = head.next;
             return ;
         }
         ListNode cur = searchPrev(key);
         //没有要删除的节点
         if (cur == null) {
             return ;
         }
          cur.next = cur.next.next;
     }
     private  ListNode searchPrev(int key) {
         ListNode cur = head;
         while (cur != null) {
             if (cur.next.val == key) {
                 cur.next = cur.next.next;
                 return cur;
             }
             cur = cur.next;
         }
         return null;
     }
    //删除所有值为key的节点
           public void removeAllKey(int key){
              if (head == null) {
                  return ;
              }
              ListNode prev = head;
              ListNode cur = head.next;
              while (cur != null) {
                  if (cur.val == key) {
                      prev.next = cur.next; //删除这个节点
                  }else {
                      prev  = cur;
                  }
                  cur = cur.next;
              }
              if (head.val == key) {
                  head = head.next;
              }
     }
     //反转链表
    public ListNode reverseList() {
             if (head == null) {
                 return null;
             }
             if (head.next == null) {
                 return head;
             }
             ListNode cur = head.next;
             head.next = null;
             while (cur != null) {
                 ListNode curNext = cur.next;
                 cur.next = head;
                 head = cur;
                 cur = curNext;
             }
             return head;
     }

    public void clear() {

         head = null;
      }
}
